Time-dependent shortest hyperpaths for dynamic routing on transit networks

This chapter introduces a unifi ed framework for the computation of shortest hyperpaths on a public transport network with timevarying performance, which ii due to road traffic and passenger congestion features like service frequency, running times, waiting times, on-board comfort and line regularity change noticeably during the day, especially in urban systems. Even where a fi xed timetable exists, it may be unknown to the passenger or be not satisfi ed in practice. So, from the user perspective, the transit service results in a mix of schedule-based and frequency-based lines. Passengers will then optimize their route choice based on the available information about service performance adopting a strategic behavior with n-trip diversions in reaction to random events. The classical static case, where the time dimension is neglected, as well as the case of simple paths, where no strategic behavior is considered, are seen as two particular instances of a more general dynamic routing problem. Both discrete and continuous representation of time are considered here. Two solution approaches are presented, namely; user trajectories and temporal layers. Extensions to departure (or arrival) time choice and to multimodal networks (e.g., with park and ride) are also provided. The proposed methodology can be applied in the context of dynamic transit assignment, as well as in the context of point-to point navigation for passenger trips.